package BinaryTreePackage;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Lzm
 * @version 1.0
 */
public class levelOrder_ {



  // 用变量size来记录每层树的元素个数
  // 队列每弹出一个节点就加入其相应的左右子节点
  public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> result = new ArrayList<>();
      if (root == null){
        return result;
      }

      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      int size = queue.size();
      // 当队列中无元素说明已经遍历结束了
      while(queue.size() != 0){
        // 当队列中有root的左右节点时, size记录的就是第二层数据的节点个数
        size = queue.size();
        // 对每一层进行处理, 队列每弹出一个节点就加入对应的左右子节点
        List<Integer> list = new ArrayList<>();
        // size的作用是记录每一层的树的个数, 如果是每次添加节点都令size++的话, 那就不是记录每一层的节点个数
        while(size != 0){
          TreeNode node = queue.poll();
          list.add(node.val);
          size--;
          if (node.left != null){
            queue.add(node.left);
          }
          if (node.right != null){
            queue.add(node.right);
          }
        }
        result.add(list);
      }
      return result;
  }
}
